package Leetcode.每日一题;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @ClassName 接雨水
 * @since: 2023/7/24 19:00
 * @auth: kirito
 * @description:
 * 终于来了  哈哈哈哈 之前偶然在鱼皮那里看到了腾讯的一个笔试题是接雨水  很经典的一道题
 * 当时看了一下，嗯  不难吧，尝试做一下，妈的怎么做啊，然后放弃了，后续时不时回头看一下，嗯 还是不会
 * 今天又来挑战一下  必拿下
 *
 * 看了一下，自己有一丢丢思路了，但是不知道对不对，没有用任何算法，单纯只是为了做出来，后面在看别的快的方法
 * 接得住：
 *      从第一个开始，找后面第一个比他大的数，中间的就是接的量 i->j   sum= a[i]-a[i+1] + a[i]-a[i+2]
 *                                                         =>a[i]*j-i-1 - (a[i+1]->a[j-1])
 * 接不住：
 *      接不住应该只有两边接不住的情况了，一直上升  一直下降  或者先上后下  两种情况就接不住
 *
 *      现在开始实现~！
 *      实现出错  思路有点小问题。。。不够精简具体 中间有n多其他情况
 *      改变一下思路=》
 *      一个下降数组 对应一个上升数组 然后从两个数组的中间向两边遍历，
 *      取差值（min（a[i],b[j]）-对应的前面那个数 然后*j-i）  最后取和
 *      也不行 哈哈哈  放弃 看解析
 *      https://leetcode.cn/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/
 **/
public class 接雨水 {
    //动态规划  思路巨牛 为什么能想到这个方法对于下标
    //这个方法还是太巧妙了  怎么会想到用这个办法的？？？左往右跟右往左我都能理解
    //只代表当前方向最多能存多少  然后取并集就是最多的接水量  但是怎么会想到并集的！！！
// 1. 计算每个位置左边的最大高度到leftMax数组
// 2. 计算每个位置右边的最大高度到rightMax数组
// 3. 循环每个位置,可接雨水量为左右最大高度中的最小值减去当前高度
// 4. 求和得到总的可接雨水量
    public static int trap(int[] height) {

        // 初始化变量
        int n = height.length;
        if (n == 0) {
            return 0;
        }

        // 定义左右最大高度数组
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        // 计算左最大高度
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        // 计算右最大高度
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        // 计算可接雨水量
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            // 当前位置可接雨水量等于左右最大高度中的最小值减去当前高度
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
    //栈实现  对照图跟着好理解
    // 1. 使用栈保存柱子索引
// 2. 从左向右遍历数组
// 3. 当前柱子高于栈顶元素时,可以计算Trap积水量
// - 计算水柱宽度
// - 计算最小高度作为界定高度
// - 累加到结果中
// 4. 当前索引入栈
// 5. 返回结果
    public static int trap2(int[] height) {

        // 使用栈来存储柱子索引
        Stack<Integer> st = new Stack<Integer>();

        // 初始化变量
        int i = 0, ans = 0;

        // 遍历数组
        while (i < height.length) {

            // 如果栈不为空,且当前柱子高于栈顶元素
            // 表示找到了一个底,可以开始计算水量
            while (!st.isEmpty() && height[i] > height[st.peek()]) {

                // 弹出栈顶元素
                int top = st.pop();

                // 如果栈空了,说明弹完了,退出循环
                if(st.isEmpty()) {
                    break;
                }

                // 计算水柱的宽度
                int distance = i - st.peek() - 1;

                // 计算界定水柱高度的最小高度
                int bound_height = Math.min(height[i], height[st.peek()]) - height[top];

                // 计算当前水柱的积水量
                ans += distance * bound_height;
            }

            // 将当前索引入栈
            st.push(i);
            i++;
        }
        return ans;
    }
    //双指针
    // 主要步骤:
// 1. 初始化左右指针和最大高度
// 2. 从两端向中间遍历
// 3. 更新左右最大高度
// 4. 从低的一端开始填充水,并移动指针
// 5. 累加总的接水量
    public static int trap3(int[] height) {

        // 初始化变量
        int ans = 0;
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;

        // 从左右两端向中间遍历
        while (left < right) {

            // 更新左右最大高度
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);

            // 从低处开始填充水,移动指针
            if (height[left] < height[right]) {
                ans += leftMax - height[left];
                ++left;
            } else {
                ans += rightMax - height[right];
                --right;
            }
        }

        return ans;
    }



}
